package com.Q04;

/**
 * @version v1.0.0
 * 创建时间：2022/6/29 14:35
 */
public class Q04_01 {
    public static void main(String[] args) {
        System.out.println(new Solution().findWhetherExistsPath(5, new int[][]{{0, 2}, {1, 3}, {1, 4}, {1, 3}, {2, 3}, {3, 4}}
                , 0
                , 4));
    }
}
class Solution {
    boolean[] visited;
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        // 正序dfs会导致多个分支无效，因此浪费时间可能导致超时
        // 因此使用从逆序的方向找到start
        visited = new boolean[graph.length];
        return dfs(graph,start,target);
    }

    private boolean dfs(int[][] graph,int s,int e){
        for (int i = 0; i < graph.length; i++) {
            if (!visited[i]) {
                if (graph[i][1]==e && graph[i][0] == s)
                    return true;
                visited[i] = true;
                if (graph[i][1] == e && dfs(graph, s, graph[i][0])) {
                    return true;
                }
                visited[i] = false;
            }
        }
        return false;
    }
}
